package com.cjm.algorithm.tanxin;

import java.util.Arrays;

public class Ti455 {
    public static void main(String[] args) {
        Ti455 ti455 = new Ti455();
        System.err.println(ti455.findContentChildren(new int[]{1, 2, 3}, new int[]{3}));
    }

    public int findContentChildren(int[] g, int[] s) {
        // 孩子i， 胃口g[i]，
        // 饼干j， 尺寸s[j]
        // s[j]>=g[i] -> j -> i
        Arrays.sort(s);
        Arrays.sort(g);

        int num = 0;
        int idex = -1;
        for (int i = 0; i < g.length; i++) {
            int i1 = g[i];
            for (int i2 = idex + 1; i2 < s.length; i2++) {
                int i3 = s[i2];
                if (i3 >= i1) {
                    idex = i2;
                    num++;
                    break;
                }
            }
        }
        return num;
    }

    public int findContentChildren2(int[] g, int[] s) {
        if (g == null || s == null) {
            return 0;
        }
        Arrays.sort(g);
        Arrays.sort(s);
        // 两个不同的索引
        int gi = 0, si = 0;
        while (gi < g.length && si < s.length) {
            if (g[gi] <= s[si]) {
                // 如果孩子的胃口小于饼干 的大小， 那么这个饼干 就是属于这个孩子了
                gi++;
            }
            // 如果月饼连最小的胃口的孩子都满足不了， 那么
            si++;
        }
        return gi;
    }

    public int findContentChildren3(int[] g, int[] s) {
        if (g == null || s == null) {
            return 0;
        }
        Arrays.sort(g);
        Arrays.sort(s);


        int result = 0;
        int sIndex = s.length - 1;

        for (int i = g.length - 1; i >= 0; i--) {
            if (sIndex >= 0 && g[i] <= s[sIndex]) {
                result++;
                sIndex--;
            }
        }
        return result;
    }
}
